from sortedcontainers import SortedList


class MRUQueue:

    def __init__(self, n: int):
        self.n = n
        self.lst = SortedList([[i, i] for i in range(1, n + 1)])

    def fetch(self, k: int) -> int:
        idx, val = self.lst.pop(k - 1)
        self.n += 1
        self.lst.add([self.n, val])
        return val


if __name__ == "__main__":
    obj = MRUQueue(8)
    print(obj.fetch(3))  # 3
    print(obj.fetch(5))  # 6
    print(obj.fetch(2))  # 2
    print(obj.fetch(8))  # 2
